package JavaLab.Collections;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class MyLinkedList implements MyList, MyQueue, MyStack{

	int size = 0;
	
	Node first;
	
	Node last;
	
	public MyLinkedList(){
	}
	
	public MyLinkedList(MyList c){
		Iterator iter = c.iterator();
		while(iter.hasNext()){
			this.addLast(iter.next());
		}
		/*for(int i = 0; i < c.size(); i++)
			this.addLast(c.get(i));*/
		/*for(Object entry : c){
			this.addLast(entry);
		}*/
	}
	
	public MyList addFirst(Object e){
		Node node = new Node(e, null, first);
		if(size == 0){
			first = last = node;
		} else {
			first.prev = node;
			first = node;
		}
		size++;
		return this;
	}
	
	public MyList addLast(Object e){
		Node node = new Node(e, last, null);
		if(size == 0){
			first = last = node;
		} else {
			last.next = node;
			last = node;
		}
		size++;
		return this;
	}
	
	public Object getFirst(){
		if(first == null) throw new NoSuchElementException();
		return first.item;
	}
	
	public Object getLast(){
		if(last == null) throw new NoSuchElementException();
		return last.item;
	}
	
	public Object removeFirst(){
		if(first == null) throw new NoSuchElementException();
		Node deleteNode = first;
		first = first.next;
		deleteNode.next = null;
		size--;
		return deleteNode.item;
	}
	
	public Object removeLast(){
		if(last == null) throw new NoSuchElementException();
		Node deleteNode = last;
		last = last.prev;
		deleteNode.prev = null;
		size--;
		return deleteNode.item;
	}
	
	public Iterator descendingIterator(){
		return new DescendingIterator();
	}
	
	private class DescendingIterator implements Iterator{
		private Node node;
		private int index;
		
		public DescendingIterator() {
			this(size());
		}
		
	    public DescendingIterator(int index){
	    	this.index = index;
			if(index == size){
				node = null;
				return;
			}
			checkElementIndex(index);
			node = atPos(index);
	    }
	    
		public boolean hasNext() {
			return index > 0;
		}

		public Object next() {
			if(node == null) return null;
			return node.prev;
		}

		public void remove() {
			node = node.prev;
			MyLinkedList.this.remove(index--);
		}
		
	}
	
	public void add(Object e) {
		addLast(e);
	}

	public void add(int index, Object e) {
		if(index == size){
			addLast(e);
			return;
		}
		checkElementIndex(index);
		Node currNode = atPos(index);
		Node newNode = new Node(e, currNode.prev, currNode);
		newNode.next.prev = newNode.prev.next = newNode;
		size++;
	}

	public void addAll(Object[] e) {
		for(Object o : e){
			addLast(o);
		}
	}

	public void addAll(int index, Object[] e) {
		if(index == size - 1){
			addAll(e);
			return;
		}
		if(index == 0){
			for(int i = e.length - 1; i >= 0; i--){
				addFirst(e[i]);
			}
			return;
		}
		checkElementIndex(index);
		Node currNode = atPos(index);
		for(int i = 0; i < e.length; i++){
			Node newNode = new Node(e[i], currNode.prev, currNode);
			newNode.prev.next = newNode.next.prev = newNode;
		}
		size += e.length;
	}

	public Object get(int index) {
		checkElementIndex(index);
		return atPos(index).item;
	}

	public Object remove(int index) {
		Node deleteNode = atPos(index);
		if(index == 0){
			first = first.next;
			deleteNode.next = null;
		} else if(index == size - 1){
			last = last.prev;
			last.next = null;
			deleteNode.prev = null;
		}
		else{
			deleteNode.prev.next = deleteNode.next;
			deleteNode.next.prev = deleteNode.prev;
			deleteNode.next = null;
			deleteNode.prev = null;
		}
		size--;
		return deleteNode.item;
	}

	public void clear() {
		for (Node x = first; x != null; ) {
            Node next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
		first = last = null;
		size = 0;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void set(int index, Object e) {
		checkElementIndex(index);
		atPos(index).item = e;
	}

	public int indexOf(Object o) {
		int index = 0;
		if(o == null){
			for(Node node = first; node != null; node = node.next, index++){
				if(node.item == null)
					return index;
			}
		} else {
			for(Node node = first; node != null; node = node.next, index++){
				if(node.item.equals(o))
					return index;
			}
		}
		return -1;
	}

	public int size() {
		return size;
	}

	public Object[] toArray() {
		Object[] result = new Object[size];
		int i = 0;
		for(Node node = first; node != null; node = node.next){
			result[i++] = node.item;
		}
		return result;
	}

	public Iterator iterator() {
		return new Itr();
	}

	private class Itr implements Iterator{
		private Node node;
		private int index;
		
		Itr(){
			node = null;
			index = -1;
		}
		
		Itr(int index){
			this.index = index;
			if(index == size){
				node = null;
				return;
			}
			checkElementIndex(index);
			node = atPos(index);
		}
		
		public boolean hasNext() {
			return index < size - 1;
		}

		public Object next() {
			index++;
			if(index == 0){
				if(size == 0) return null;
				return (node = atPos(0)).item;
			}
			if(node == null) return null;
			return (node = node.next).item;
		}

		public void remove() {
			node = node.next;
			MyLinkedList.this.remove(index++);
		}
		
	}
	
	private void checkElementIndex(int index){
		if(index < 0 || index >= size)
			throw new MyIndexOutOfBoundsException();
	}
	
	private Node atPos(int index){
		checkElementIndex(index);
		Node node = first;
		for(int i = 0; i < index; i++)
			node = node.next;
		return node;
	}
	
	private static class Node{
		Object item;
		Node next;
		Node prev;
		
		Node(Object item, Node prev, Node next){
			this.item = item;
			this.prev = prev;
			this.next = next;
		}
	}

	public void offer(Object e) {
		add(e);
	}

	public Object peek() {
		return getFirst();
	}

	public Object poll() {
		Object result = getFirst();
		removeFirst();
		return result;
	}

	public void push(Object e) {
		add(e);
	}

	public Object pop() {
		Object result = getLast();
		removeLast();
		return result;
	}
}
